Computerized devices control almost every aspect of our life—from writing documents to controlling traffic lights. However, computerized devices are bug-prone, and thus require a testing phase in which the bugs should be discovered. The testing phase is considered one of the most difficult tasks in designing a computerized device. The cost of not discovering a bug may be enormous, as the consequences of the bug may be disastrous. For example, a bug may cause the injury of a person relying on the designated behavior of the computerized device. Additionally, a bug in hardware or firmware of a marketed product may be expensive to fix, as patching it requires call-back of the computerized device. Hence, many developers of computerized devices invest a substantial portion of the development cycle in discovering erroneous behaviors of the computerized device.
A specific problem in testing relates to hardware or software products that need to comply with specification that includes transactions. Such products may include multiple processor or multiple thread architectures which utilize transactional memory. Software examples may include environments such as Java Virtual Machines (JVMs) that support Java with transactions, and database management systems that support transactions.
In the current context, the term transaction generally refers to a construct in hardware or software interface that encapsulates a set of instructions. Transactions can be used by one or more concurrent or parallel processes using a shared resource. It will be appreciated, however, that the term concurrency may relate to pseudo-concurrency, such as, for example, a mechanism wherein one processor performs two or more software processes intermittently.
The operations comprised by the transaction have to appear to be performed atomically, i.e., either all or none are performed, without observable collisions with another process performing an operation therebetween, such as accessing the resources associated with the transaction. For example, a non-atomic procedure for transferring money may comprise several operations: reading the debited account balance, deducting the transferred amount from the balance, reading the credited account balance, and crediting the transferred amount. If the procedure is performed in a non-atomic manner, after the debited account balance is read, another concurrent process may change the balance, thereby the final determined balance would be wrong. In the case of hardware, the hardware design may implement transactions by tracking global accesses to transactional resources and aborting and retrying a transaction when a collision is detected. Other manners of implementing transactions may utilize obtaining a software or hardware lock, using mutual exclusion object (mutex), or the like.
Some transaction specifications also require that all the transactions in the application are serializable, i.e., the transactions appear to all processes to be ordered in a consistent way.
Verifying that an implementation of a product adheres with the atomicity and serialization requirements is similar to but harder than checking memory coherency. The current problem is harder since it may involve multiple accesses to multiple memory locations in a single transaction. Also, known methods for memory coherency verification relate to checking that a given test adheres with the requirements. However, the degree to which the test indeed checks the atomicity and serialization is up to the test designer. In addition, the efficiency and scalability of such solutions may not be satisfactory, i.e., as more processes are performed in parallel, the testing time or complexity may increase to non-practical values.